package com.demo.java.OD251_300.OD261;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【高速公路休息站充电规划】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146058879
 */
public class OdMain {
    // 电量数组和充电时间数组
    static int[] pd;
    static int[] pt;
    // 存储中间计算结果，避免重复计算
    static HashMap<String, Integer> memo;

    // 动态规划递归函数
    public static int dp(int pow, int dis, int N) {
        // 如果电量足够，直接返回需要的充电时间
        if (pow >= dis) {
            return dis / 100;
        }

        // 使用当前电量和剩余距离作为key，查找是否已有结果
        String key = pow + "," + dis;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int res = Integer.MAX_VALUE;
        int can = dis - pow;

        // 遍历所有充电桩
        for (int i = 0; i < N; i++) {
            if (can > pd[i]) {
                continue;
            }
            if (pd[i] == dis) {
                continue;
            }

            int power_d = pd[i];
            int power_t = pt[i];

            // 如果电量无法满足行驶要求，跳过
            if (dp(1000, power_d, N) == -1) {
                continue;
            }

            // 计算从当前位置到目标的充电时间
            int tmp = (dis - power_d) / 100 + power_t + 1 + dp(1000, power_d, N);
            res = Math.min(res, tmp);
        }

        // 如果没有找到合适的路径，返回-1
        if (res == Integer.MAX_VALUE) {
            res = -1;
        }

        // 将计算结果存入memo，避免重复计算
        memo.put(key, res);
        return res;
    }

    // 主函数，输入数据并调用动态规划方法
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int D = scanner.nextInt(); // 目标距离
        int n = scanner.nextInt(); // 充电桩数量

        // 初始化充电桩的电量和充电时间
        pd = new int[n];
        pt = new int[n];
        memo = new HashMap<>();

        // 输入每个充电桩的电量和充电时间
        for (int i = 0; i < n; i++) {
            pd[i] = D - scanner.nextInt();
            pt[i] = scanner.nextInt();
        }

        // 输出最短充电时间
        System.out.println(dp(1000, D, n));
        scanner.close();
    }
}